import java.util.*;

public class Stacks {
    public static void main(String[] args) {
        Deque<String> stack = new LinkedList<>();
        Deque<String> tmp = new LinkedList<>(stack);

        stack.push('*' + "");
        System.out.println(stack.getLast());
        stack.removeLast();
        System.out.println(0 - 2147483647);
        System.out.println(stack.size());
        System.out.println(stack.peek());

        StringBuilder s = new StringBuilder("11");
        StringBuilder s1 = new StringBuilder("11");

        System.out.println(Math.pow(2, 3));

        int i = Integer.parseInt("111");
        System.out.println(i);
        s1.delete(0, s1.length());
        System.out.println(s1);
        System.out.println((int) '0');
        System.out.println(42 =='*');

        System.out.println(s.toString().equals(s1.toString()));
        System.out.println();
    }

    /**
     * 验证栈序列
     *
     */
    //俩个指针来当作栈
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        int i = 0, j = 0, pushSize = 0, popSize = 0;
        while(i < n && j < n && pushSize != n){
            //为添加完
            if((i < 0 && pushSize < n) || pushed[i] != popped[j]){
                i++;
                while(i < n && pushed[i] == -1) i++;
                pushSize++;
            }if(pushed[i] == popped[j]){
                pushed[i] = -1;
                while(i >= 0 && pushed[i] == -1) i--;
                j++;
                popSize++;
            }
        }
        i--;
        while(i >= 0 && j < n && pushed[i] == popped[j]){
            while(i >= 0 && pushed[i] == -1) i--;
            j++;
            popSize++;
        }
        if(popSize == n) return true;
        return false;
    }
    /**
     * 字符串解码
     */
    public String decodeString(String _s) {
        char[] s = _s.toCharArray();
        Deque<String> strings = new LinkedList<>();
        Deque<Integer> ints = new LinkedList<>();
        StringBuilder curS = new StringBuilder();
        int v = 0;
        for(char c : s){
            if(c >= '0' && c <= '9'){
                v *= 10;
                v += c - '0';
            }else if(c >= 'a' && c <= 'z'){
                curS.append(c);
            }else if(c == '['){//将字符串和数据都添加
                ints.push(v);
                strings.push(curS.toString());
                v = 0;
                curS = new StringBuilder();
            }else{//] 那就复制 并把复制好的和前一个合并
                StringBuilder tmp = new StringBuilder();
                int times = ints.pop();
                for(int i = 0; i < times; i++){
                    tmp.append(curS);
                }
                curS = new StringBuilder(strings.pop() + tmp.toString());
            }
        }
        return curS.toString();
    }

    /**
     * 基本计算器 II
     */
    public int calculate(String _s) {
        Deque<Integer> stack = new LinkedList<>();
        char[] s = _s.toCharArray();
        stack.push(0);
        int n = s.length;
        char oper = '+';
        for(int i = 0; i < n; i++){
            //获得一个数字
            if(s[i] >= '0' && s[i] <= '9'){
                int pow = 0;
                int v = 0;
                while(i < n  && s[i] >= '0' && s[i] <= '9'){
                    v *= 10;
                    v += s[i++] - '0';
                    pow++;
                }
                operation(stack, v, oper);
                i--;
            }else if(s[i] == ' '){
                continue;
            }else{
                oper = s[i];
            }
        }
        int ret = 0;
        while(!stack.isEmpty()){
            ret += stack.pop();
        }
        return ret;
    }

    void operation(Deque<Integer> stack, int v2, char oper){
        if(oper == '-'){
            stack.push(v2 * -1);
        }else if(oper == '+'){
            stack.push(v2);
        }else if(oper == '*'){
            int v1 = stack.pop();
            stack.push(v1 * v2);
        }else{
            int v1 = stack.pop();
            stack.push(v1 / v2);
        }
    }
    /**
     *  比较含退格的字符串
     */
    public boolean backspaceCompare(String _s, String _t) {
        char[] ss = _s.toCharArray();
        char[] tt = _t.toCharArray();
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        int i = 0;
        int j = 0;
        while (i < ss.length || j < tt.length) {
            if (i < ss.length) {
                char s = ss[i];
                if (s == '#') {
                    if (s1.length() > 0)
                        s1.deleteCharAt(s1.length() - 1);
                } else {
                    s1.append(s);
                }
                i++;
            }
            if (j < tt.length) {
                char t = tt[j];
                if (t == '#') {
                    if (s2.length() > 0)
                        s2.deleteCharAt(s2.length() - 1);
                } else {
                    s2.append(t);
                }
                j++;
            }
        }
        return s1.toString().equals(s2.toString());
    }
    /**
     * 删除字符串中的所有相邻重复项
     */
    public String removeDuplicates(String s) {
        StringBuilder ret = new StringBuilder();
        char[] cc = s.toCharArray();
        for(char c : cc){
            if(ret.length() > 0 && c == ret.charAt(ret.length() - 1)){
                ret.deleteCharAt(ret.length() - 1);
            }else{
                ret.append(c);
            }
        }
        return ret.toString();
    }
}
